#include<bits/stdc++.h>
using namespace std;

int a[1010000] = {0, 1, 2};

int main()
{
	for(int i = 3;i < 1000000;i++)
		a[i] = (2*a[i-1]+a[i-2])%32767;
	
	int k, t;
	cin>>t;
	while(t--)
	{
		cin>>k;
		cout<<a[k]<<endl;
	}
	cout<<endl;
	system("pause"); 
	return 0;
}

